/* =============================================================
 * Your Grandmother's guide to Algorithms
 * =============================================================
 *
 * Copyright (c) 2007, Saverio Miroddi
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *     * Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright 
 *       notice, this list of conditions and the following disclaimer in the 
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the SaverioMiroddiSoftware nor the names of its 
 *       contributors may be used to endorse or promote products derived from 
 *       this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER 
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *  
 * ---------------------------
 * MergeSort.java
 * ---------------------------
 *
 */
package merge;

import heaps.Heap;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import utils.Utils;

/**
 * Merge sorting, with custom division factor.
 * 
 * @author Saverio Miroddi
 */
public class MergeSort
{
	/**
	 * Entry point; the same 
	 * 
	 * @param array
	 *            input data
	 * @param divisionFactor
	 *            recursion stops when the current array has this number of
	 *            elements, and sort them "in memory".
	 */
	public static <T extends Comparable<T>> T[] sort(
			T[] array, int divisionFactor)
	{
		if (array.length < divisionFactor) {
			// stop condition for the recursion. if DIVISION_FACTOR is 2,
			// we just return the array without sorting.
			Arrays.sort(array);
			return array;
		}
		else {
			T[][] subArrays = Utils.split(divisionFactor, array);
			
			for (int i = 0; i < subArrays.length; i++)
				subArrays[i] = sort(subArrays[i], divisionFactor);

			T[] sorted = iterativeSort(subArrays);
			
			return sorted;
		}
	}

	/**
	 * Bery funny. More generally, using OO we should create an ArrayIterator
	 * class, which was implemented in rev 168.
	 */
	@SuppressWarnings("unchecked")
	private static <T extends Comparable<T>> T[] iterativeSort(T[]... sources)
	{
		List<T> sorted = new ArrayList<T>();
		
		Heap<T[]> heap = new Heap<T[]>() {
			@Override
			protected boolean isTop(T[] arr0, T[] arr1)
			{
				return arr0[0].compareTo(arr1[0]) < 0;
			}
		};
		for (T[] source : sources) heap.insert(source);
	
		while (heap.size() > 0) {
			T[] nextSource = heap.extractTop();
			sorted.add(nextSource[0]);
			nextSource = Arrays.copyOfRange(nextSource, 1, nextSource.length);
			
			if (nextSource.length > 0) heap.insert(nextSource);
		}
		
		// what the h.ll!!!!
		Class<?> klazz = sources.getClass().getComponentType().getComponentType();
		return sorted.toArray((T[])Array.newInstance(klazz, 0));
	}
}